// tests/maze_search_test.cpp
//
// 该测试文件验证 maze_dfs.h 与 maze_bfs.h 中实现的深度优先搜索（DFS）
// 和广度优先搜索（BFS）两种迷宫路径搜索算法的正确性、最短性以及在
// 不同边界条件下的鲁棒性。
//
// 覆盖点摘要：
//   1. 基础可行路径与最短路径验证。
//   2. DFS 与 BFS 结果对比，确保 DFS 不会比 BFS 更短。
//   3. 起点/终点阻塞等无解情形。
//   4. 多条最短路径、复杂走廊、开放网格等典型场景。
//   5. 辅助函数 PathIsValid 用于统一检查路径有效性。

#include <cstdlib>
#include <gmock/gmock.h>
#include <gtest/gtest.h>

#include "bfs/maze_bfs.h"
#include "dfs/maze_dfs.h"

using ::testing::ElementsAreArray;
using ::testing::SizeIs;

namespace {

/// 检查给定路径是否符合以下条件：
///   - 起点为 (0,0)，终点为 (rows-1, cols-1)。
///   - 所有节点在迷宫范围内且可通行。
///   - 相邻节点之间的曼哈顿距离为 1（只能上下左右移动）。
bool PathIsValid(const std::vector<std::vector<int>>& maze,
                 const std::vector<Maze::Cell>& path) {
  if (maze.empty() || maze[0].empty()) {
    return path.empty();
  }
  if (path.empty()) {
    return false;
  }

  const int rows = static_cast<int>(maze.size());
  const int cols = static_cast<int>(maze[0].size());

  const Maze::Cell expectedStart{0, 0};
  const Maze::Cell expectedGoal{rows - 1, cols - 1};

  if (!(path.front() == expectedStart)) {
    return false;
  }
  if (!(path.back() == expectedGoal)) {
    return false;
  }

  auto inBounds = [&](const Maze::Cell& cell) {
    return cell.row >= 0 && cell.col >= 0 && cell.row < rows &&
           cell.col < cols;
  };

  for (std::size_t i = 0; i < path.size(); ++i) {
    const Maze::Cell& cell = path[i];
    if (!inBounds(cell) || maze[cell.row][cell.col] != 0) {
      return false;
    }
    if (i > 0) {
      const Maze::Cell& prev = path[i - 1];
      const int dr = cell.row - prev.row;
      const int dc = cell.col - prev.col;
      const int manhattan = std::abs(dr) + std::abs(dc);
      if (manhattan != 1) {
        return false;
      }
    }
  }
  return true;
}

/// 基础用例：验证 BFS 在简单迷宫中返回已知最短路径。
TEST(MazeSearchTest, BreadthFirstSearchFindsShortestPath) {
  const std::vector<std::vector<int>> maze = {
      {0, 0, 0},
      {1, 1, 0},
      {0, 0, 0},
  };

  const auto path = Maze::breadthFirstSearch(maze);
  const std::vector<Maze::Cell> expected = {
      {0, 0}, {0, 1}, {0, 2}, {1, 2}, {2, 2},
  };

  ASSERT_FALSE(path.empty());
  EXPECT_TRUE(PathIsValid(maze, path));
  EXPECT_THAT(path, ElementsAreArray(expected));
}

/// DFS 应找到某条可行路径，但长度不应短于 BFS 的最短路径。
TEST(MazeSearchTest, DepthFirstSearchProducesNonShorterPathThanBfs) {
  const std::vector<std::vector<int>> maze = {
      {0, 0, 1, 0},
      {1, 0, 1, 0},
      {1, 0, 0, 0},
      {1, 1, 1, 0},
  };

  const auto dfsPath = Maze::depthFirstSearch(maze);
  const auto bfsPath = Maze::breadthFirstSearch(maze);

  ASSERT_FALSE(dfsPath.empty());
  ASSERT_FALSE(bfsPath.empty());

  const Maze::Cell expectedStart{0, 0};
  const Maze::Cell expectedGoal{3, 3};

  EXPECT_TRUE(PathIsValid(maze, dfsPath));
  EXPECT_TRUE(PathIsValid(maze, bfsPath));
  EXPECT_EQ(dfsPath.front(), expectedStart);
  EXPECT_EQ(dfsPath.back(), expectedGoal);
  EXPECT_GE(static_cast<int>(dfsPath.size()),
            static_cast<int>(bfsPath.size()));
}

/// 起点被阻塞时，应立即返回空路径。
TEST(MazeSearchTest, BlockedEntranceReturnsEmptyForBothAlgorithms) {
  const std::vector<std::vector<int>> maze = {
      {1, 0, 0},
      {0, 0, 0},
      {0, 0, 0},
  };

  EXPECT_TRUE(Maze::depthFirstSearch(maze).empty());
  EXPECT_TRUE(Maze::breadthFirstSearch(maze).empty());
}

/// 复杂走廊迷宫：检验 BFS 能绕开障碍并得到正确的最短路线。
TEST(MazeSearchTest, BreadthFirstSearchNavigatesComplexCorridor) {
  const std::vector<std::vector<int>> maze = {
      {0, 0, 1, 0, 0, 0},
      {1, 0, 1, 0, 1, 0},
      {1, 0, 0, 0, 1, 0},
      {1, 1, 1, 0, 1, 0},
      {0, 0, 0, 0, 1, 0},
      {0, 1, 1, 1, 0, 0},
  };

  const auto path = Maze::breadthFirstSearch(maze);
  const std::vector<Maze::Cell> expected = {
      {0, 0}, {0, 1}, {1, 1}, {2, 1}, {2, 2}, {2, 3},
      {1, 3}, {0, 3}, {0, 4}, {0, 5}, {1, 5}, {2, 5},
      {3, 5}, {4, 5}, {5, 5},
  };

  ASSERT_FALSE(path.empty());
  EXPECT_TRUE(PathIsValid(maze, path));
  EXPECT_THAT(path, ElementsAreArray(expected));
}

/// 验证 DFS 的“向右优先”顺序会产生预期的路径形状。
TEST(MazeSearchTest, DepthFirstSearchRespectsRightFirstPriority) {
  const std::vector<std::vector<int>> maze = {
      {0, 0, 0, 0},
      {0, 1, 1, 0},
      {0, 0, 0, 0},
  };

  const auto dfsPath = Maze::depthFirstSearch(maze);
  const std::vector<Maze::Cell> expected = {
      {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 3}, {2, 3},
  };

  ASSERT_FALSE(dfsPath.empty());
  EXPECT_TRUE(PathIsValid(maze, dfsPath));
  EXPECT_THAT(dfsPath, ElementsAreArray(expected));
}

/// 开放网格：最短路径应为行列之和减一（纯直线）。
TEST(MazeSearchTest, BreadthFirstSearchOpenGridHasMinimalLength) {
  const int rows = 8;
  const int cols = 8;
  const std::vector<std::vector<int>> maze(rows,
                                           std::vector<int>(cols, 0));

  const auto path = Maze::breadthFirstSearch(maze);

  ASSERT_FALSE(path.empty());
  EXPECT_TRUE(PathIsValid(maze, path));

  const int expectedLength = rows + cols - 1;
  EXPECT_EQ(static_cast<int>(path.size()), expectedLength);
}

/// 终点被围堵：两种算法都应检测到无路径。
TEST(MazeSearchTest, BreadthFirstSearchDetectsNoPathWhenExitIsTrapped) {
  const std::vector<std::vector<int>> maze = {
      {0, 0, 0, 0},
      {0, 1, 1, 0},
      {0, 1, 1, 0},
      {0, 0, 0, 1},
  };

  EXPECT_TRUE(Maze::breadthFirstSearch(maze).empty());
  EXPECT_TRUE(Maze::depthFirstSearch(maze).empty());
}

/// 大型迷宫包含多个死胡同，确保 BFS 能找到最短路径并与 DFS 对比。
TEST(MazeSearchTest, LargeMazeWithDeadEndsPrefersShortestRoute) {
  const std::vector<std::vector<int>> maze = {
      {0, 0, 1, 1, 1, 1},
      {1, 0, 0, 0, 0, 1},
      {1, 0, 1, 1, 0, 1},
      {1, 0, 1, 1, 0, 1},
      {1, 0, 0, 0, 0, 1},
      {1, 1, 1, 1, 0, 0},
  };

  const auto bfsPath = Maze::breadthFirstSearch(maze);
  const auto dfsPath = Maze::depthFirstSearch(maze);

  ASSERT_FALSE(bfsPath.empty());
  ASSERT_FALSE(dfsPath.empty());

  EXPECT_TRUE(PathIsValid(maze, bfsPath));
  EXPECT_TRUE(PathIsValid(maze, dfsPath));

  const int expectedBfsLength = 11; // 预先计算的最短路径节点数。
  EXPECT_EQ(static_cast<int>(bfsPath.size()), expectedBfsLength);
  EXPECT_GE(static_cast<int>(dfsPath.size()), expectedBfsLength);
}

/// 多条最短路线的迷宫：BFS 虽可以返回任意一条，但长度需匹配最优解。
TEST(MazeSearchTest, BreadthFirstSearchHandlesMultipleOptimalRoutes) {
  const std::vector<std::vector<int>> maze = {
      {0, 0, 0, 0},
      {0, 1, 1, 0},
      {0, 0, 0, 0},
      {0, 1, 1, 0},
  };

  const auto path = Maze::breadthFirstSearch(maze);

  ASSERT_FALSE(path.empty());
  EXPECT_TRUE(PathIsValid(maze, path));

  const int expectedLength = 7;
  EXPECT_EQ(static_cast<int>(path.size()), expectedLength);
}

/// 单格迷宫：入口即出口，路径长度应为 1。
TEST(MazeSearchTest, SingleCellMazeReturnsTrivialPath) {
  const std::vector<std::vector<int>> maze = {
      {0},
  };

  const auto dfsPath = Maze::depthFirstSearch(maze);
  const auto bfsPath = Maze::breadthFirstSearch(maze);

  ASSERT_THAT(dfsPath, SizeIs(1));
  ASSERT_THAT(bfsPath, SizeIs(1));

  const Maze::Cell single{0, 0};
  EXPECT_EQ(dfsPath.front(), single);
  EXPECT_EQ(bfsPath.front(), single);
}

} // namespace

/// gtest/gmock 统一入口。
int main(int argc, char** argv) {
  ::testing::InitGoogleMock(&argc, argv);
  return RUN_ALL_TESTS();
}